The Reed Solomon (RS) code is widely used for error detection and correction in many applications in which transmitted data is likely to be corrupted by noise or other error sources (e.g., cellular phones, satellite communications, CD players). The RS code is a block code. In such codes, a fixed number of information symbols are utilized to generate a predefined number of check symbols that are added to the information symbols to generate a code word.
RS codes are usually referred to as RS (n,k) codes, wherein n is the total number of symbols comprising a code word, and k is the number of information symbols in the code word. In systematic codes, a code word is formed from k information symbols and trailing check symbols, i.e., the information symbols are transmitted prior to the check symbols. The check symbols are generated utilizing the k information symbols, and are actually the parity information of the information symbols.
The generation of an RS code is based on Galois Field (GF) arithmetic, the size of the GF being determined by the number of bits per symbol, e.g., codes in which a symbol is comprised from m bits are based on a GF of size n=2m, and are signed as follows, GF(2m). The order of the GF elements is defined by the field polynomial, which is normally specified using a conventional polynomial representation. In GFs, it is customary to represent the code symbols in the form of polynomials, wherein the Most Significant Bit (MSB) is utilized as a coefficient for the polynomial term of the highest order, and the Least Significant Bit (LSB), for the coefficient of the polynomial term of the lowest order.
Throughout the following discussion, the encoding process will be described in terms of polynomial manipulations. To prevent confusion, polynomials that utilize symbols as their coefficients (symbol level polynomials) will be represented as functions of >z′. Polynomials that utilize binary bits as their coefficients (bit level polynomials) will be represented as functions of >x′.
In GFs, arithmetic addition and multiplication are carried out as follows: addition (and subtraction) is performed as an Exclusive OR (XOR) operation; and multiplication of two symbols is calculated as the multiplication result modulo the field polynomial, such that multiplication of two polynomials a(x) and g(x) over a GF with a field polynomial f(x) equals (a(x)·g(x)) mod f(x).
The generation of the RS code check symbols (also known as parity symbols) is carried out utilizing a generator polynomial
      G          (      z      )        =            ∑              j        =        0                    n        -        k        -        1              ⁢                  g        j            ·                        z          j                ′            which is of order n−k−1. If representing the information symbols of a code word as the polynomial
      I          (      z      )        =            ∑              q        =        0                    k        -        1              ⁢                  i        q            ·              z        q            i.e., a code word consisting of k information symbols iq, (q=0, 1, Y, k−1), then the calculation of the code word check symbols in a systematic RS code is carried out as follows—p(z)=(I(z)·zn−k)mod G(z)  (*)wherein p(z) is the polynomial representing the parity symbols. There are a large number of available coding algorithms and techniques that carry out the finite field arithmetic disclosed in equation (*), but due to performance requirements, it is necessary to develop these algorithms in hardware rather than software (hardware implementations are substantially faster than the software implementations).
One method for a GF multiplier is disclosed in U.S. Pat. No. 4,567,568 wherein the GF multiplication is based on a so-called look-up table method. Such methods take advantage of the finite nature of GFs. Because the number of elements in a GF is finite, and since any multiplication result also belongs to the GF, a look-up table of multiplication of all of the field elements may be constructed and stored in a memory device. These types of methods are attractive for software implementation. Hardware implementations of such methods, however, are complex and burdensome, and generally unacceptable.
FIG. 1 schematically illustrates the conventional architecture for a systematic RS(n,k) encoder 100, the so-called “parallel encoder”. The encoder 100 is designed to generate m bit symbols, utilizing the information symbols, which are also m bits in length. The check symbols generation is performed according to the finite field arithmetic operations that are disclosed in equation (*), over the GF(2m) defined by the field polynomial f(x).
The check symbols calculation is performed through a series of multipliers Mul0–Muln−k−1, and adders Add0–Addn−k−1. Each of the registers R0–Rn−k−1, can hold an m bit symbol. The registers R0–Rn−k−1, are connected in series, a connection that forms a so-called stage shift register. Between any two consecutive registers, there are XOR gates, which are numerated as Add0–Addn−k−1, for finite field addition. The finite field multipliers Mul0–Muln·k−1, perform multiplication of the feedback signal a(x) present on a line 130 and the RS (n,k) generator polynomial coefficients, g0(x), g1(x), Y,gn−k−1(x) (these are all m bit symbols). The result of the multiplication P0−Pn−k−1 is input to the adders Add0–Addn−k−1.
An arbitration mechanism 135 is utilized to select the first k information symbols at an encoder input 133 to be transmitted prior to the check symbols through an encoder output 132. Another arbitration mechanism 136 is utilized to provide the feedback signal on the feedback line 130 to the encoder multipliers Mul0–Muln−k−1 (i.e., in the conducting state while the information symbols are input). Each information symbol that enters the encoder is transmitted on the encoder output 132, and at the same time used to calculate the feedback signal on the line 130 by the addition (performed by Addn−k−1) with the content of the last register Rn−k−1.
The check symbol calculation is carried out by feeding the encoder “Data In” input 133 with the information symbols, iq(x)(q=0, 1, Y, k−1), one at a time. As the information symbols are fed into the encoder 100 at the input 133, the corresponding feedback signal a(x) is determined by the adder Addn·k−1, and applied on the feedback line 130. The feedback signal on 130 is multiplied in the encoder multipliers Mul0–Muln−k−1 by each of the RS generator polynomial coefficients g0(x),g1(x),Y,gn−k−1(x). The multiplication result is then introduced to the adders Add0–Addn−k−2 (except for the output from Mul0, which is fed directly to R0), which performs addition with the content of the registers R0–Rn−k−2.
After all the information symbols have entered the encoder 100, the encoder registers R0–Rn−k−1 are set to the values of the registers R0–Rn−k−1 content (i.e. the check symbols), the arbitration mechanisms 135 and 136 change state to cut off the feedback signal on the line 130 from entering the multipliers Mul0–Muln−k−1, and enable the transmission of the check symbols on the output 132 through register Rn−k−1 and the adder Addn−k−1. At this stage, the encoder input is fed with n−k zero symbols so that the encoder performs as a regular shift register.
A conventional Galois multiplier 200 is schematically illustrated in FIG. 2. The multiplier 200 receives two polynomials (each polynomial being an m bit symbol) as inputs. To exemplify the encoder multiplier, the input polynomials are taken to be the feedback signal a(x) and one of the RS code polynomial coefficient gj(x) (the bits comprising the coefficient gj(x) are designated as gj(0), gj(1),Y,gj(m−1)). The multiplier output is the finite field multiplication result, pj(x)=(a(x)·g(x)) mod f(x), wherein f(x) is the GF(2m) polynomial. The method utilized in multiplier 200 is based on the summation of the partial products:
                                          p                          j              ⁡                              (                x                )                                              =                    ⁢                                    a              ⁡                              (                x                )                                      ·                                          ∑                                  l                  =                  0                                                  m                  -                  1                                            ⁢                                                g                  j                                      (                    l                    )                                                  ⁢                                  x                  t                                ⁢                mod                ⁢                                                                  ⁢                                                      f                    ⁡                                          (                      x                      )                                                        t                                                                                                  =                    ⁢                                                                      g                  j                                      (                    0                    )                                                  ⁡                                  [                                                            a                      ⁡                                              (                        x                        )                                                              ⁢                                          x                      0                                                        ]                                                            mod                ⁢                                                                  ⁢                                  f                  ⁡                                      (                    x                    )                                                                        +                                                            g                  j                                      (                    l                    )                                                  ⁡                                  [                                                            a                      ⁡                                              (                        x                        )                                                              ⁢                                          x                      1                                                        ]                                                            mod                ⁢                                                                  ⁢                                  f                  ⁡                                      (                    x                    )                                                                        +            …            +                                                            g                  j                                      (                                          m                      -                      1                                        )                                                  ⁡                                  [                                                            a                      ⁡                                              (                        x                        )                                                              ⁢                                          x                                              m                        -                        1                                                                              ]                                                            mod                ⁢                                                                  ⁢                                  f                  ⁡                                      (                    x                    )                                                                                            ⁢        The partial products, [aj(l)xl] mod f(x) are performed utilizing the blocks [[MN0,]] MN1,Y, MNm−1 [[−1]], which will be referred herein after as Multiplication Networks (MN). The operation and structure of the MNs are fairly well known in the art and described in U.S. Pat. No. 4,037,093. Therefore, the structure and operation will not be discussed in detail, for purposes of brevity. The MN outputs and the bits comprising the code polynomial coefficients gj(x) (0 [[529 ]] j [[| |]] n−k−1), gj(0), gj(1),γ,gj(m−1), are multiplied in the ENB0–ENBm−1 units utilizing the logical AND gates, a0–am−1. The output of the ENB0–ENBm−1 units is now added in LSB to MSB order by the adders, XOR0–XORm−1, wherein XOR0 generates the LSB of pj(x) (i.e., pj(0)), and XORm−1 generates the MSB of pj(x) (i.e., pj(m−1)).
In a conventional RS(n,k) encoder having symbols of m bits, the number of multipliers 200 is n−k. In each multiplier 200 there are m−1 MNs. The MNs comprise XOR gates, which are complex and costly implementations in terms of hardware means. It is therefore desirable to reduce the number of XOR gates required in such implementations. Additionally, in a conventional RS encoder, the parallel operation of the system allows no flexibility in the determination of the encoding rate, other than changing the clock pulse rate.
All the methods described above for the conventional RS encoder implementations utilizing GF multipliers generally require high numbers of gates. Accordingly, there exists a need for an RS encoder and method of block encoding utilizing a single GF multiplier to perform a plurality of GF multiplication operations.